// 给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。



// 注意：

// 对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
// 如果 s 中存在这样的子串，我们保证它是唯一的答案。

/**
 * @param {string} s
 * @param {string} t
 * @return {string}
 */
var minWindow = function (s, t) {
    const need = {}, win = {};

    for (let item of t) {
        need[item] = (need[item] || 0) + 1;
    }
    // 快慢指针
    let slow = 0, fast = 0;
    // 
    let valid = 0;
    // 答案 开始下标以及长度
    let start = 0, len = Number.MAX_SAFE_INTEGER;

    while (fast < s.length) {
        // 当前进入窗口的字符（右移）
        const willin = s[fast++];
        // 当前字符为必须的字符
        if (need[willin]) {
            win[willin] = (win[willin] || 0) + 1;
            if (win[willin] === need[willin]) {
                valid++;
            }
        }
        // 当valid等于所需字符键数量时 则当前窗口包含所有所需字符 当右移慢指针
        while (valid === Object.keys(need).length) {
            // console.log(fast, slow, fast - slow)
            if (fast - slow < len) {
                start = slow;
                len = fast - slow;
            }
            // 即将离开并且之后 右移
            const willOut = s[slow++];
            // 该字符在统计范围内时
            if (need[willOut]) {
                if (win[willOut] === need[willOut]) {
                    valid--;
                }
                win[willOut]--;
            }
        }

        // console.log(need, win)
    }

    return len === Number.MAX_SAFE_INTEGER ? '' : s.slice(start, start + len)
};

module.exports = minWindow;